package leetcode_题库;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/25 8:56 星期四
 */
public class _20_有效的括号 {
    public static void main(String[] args) {
        System.err.println(isValid("{[]}"));
    }

    /**
     * 栈思想
     * > 2022/08/25 09:28:05
     * 解答成功:
     * 	执行耗时:1 ms,击败了98.87% 的Java用户
     * 	内存消耗:39.4 MB,击败了60.36% 的Java用户
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        //创建一个栈，栈具有先入后出原则，可以进行括号匹配
        Stack<Character> stack = new Stack<>();
        //将字符串转为字符数组
        char[] chars = s.toCharArray();
        //遍历
        for (char c : chars) {
            //防止空指针，三元表达式，若栈为空则以*临时替补
            char stackItem = stack.isEmpty() ? '*' : stack.peek();
            //使用switch case，default就是({[，若匹配到尾，当头与peek一致，则pop，否则return false
            switch (c){
                case ']':
                    if (stackItem != '['){
                        return false;
                    }
                    stack.pop();
                    break;
                case ')':
                    if (stackItem != '('){
                        return false;
                    }
                    stack.pop();
                    break;
                case '}':
                    if (stackItem != '{'){
                        return false;
                    }
                    stack.pop();
                    break;
                default:
                    stack.push(c);
            }
        }
        //若完全匹配，则栈必为空
        return stack.isEmpty();
    }
}
